'''
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。




'''
#解题思路，最开始考虑的递归，因为子问题之间有一定的相似性。这里使用动态规划的方法，

#动态规划：动态规划算法的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他的算法。


#假设用n个节点组成的二叉树共有G(n)个，G(n)=f(1)+f(2)+⋯+f(n)。
# 又因：
# f(i)=G(i−1)∗G(n−i)，表示以i为根节点，其左子树的种类加上其右子树的种类。

#注意这里i左边的点一定比i小，共有i-1个点，i右边的点一定比i大，共n-i个点
#dp[0]=1,dp[1]=1
#
# 作者：wu_yan_zu
# 链接：https://leetcode-cn.com/problems/unique-binary-search-trees/solution/qia-te-lan-shu-dong-tai-gui-hua-python3-by-zhu_shi/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。



class Solution:
    def numTrees(self, n: int) -> int:
        if n==0:
            return 0
        dp=[0]*(n+1)
        dp[0]=1
        dp[1]=1
        for i in range(2,n+1):
            for j in range(0,i):
                dp[i]+=dp[j]*dp[i-j-1]
        return dp[-1]